import { right } from "@antv/x6/lib/registry/port-layout/line";
import { isInteger } from "lodash";
import { off } from "process";
import { start } from "repl";

/**
 * @link https://leetcode.cn/problems/merge-sorted-array/?envType=study-plan-v2&id=top-interview-150
 */
function merge(nums1: number[], m: number, nums2: number[], n: number): void {
  let index = nums1.length - 1;
  let p = m - 1;
  let q = n - 1;
  if (m === 0) {
    nums1 = nums2;
  } else {
    while (q >= 0) {
      if (nums2[q] >= nums1[p]) {
        nums1[index] = nums2[q];
        q--;
      } else {
        nums1[index] = nums1[p];
        p--;
      }
      index--;
      if (p < 0) {
        nums1.splice(0, index + 1, ...nums2.slice(0, q + 1));
        break;
      }
    }
  }
  console.log(nums1);
}

/**
 * @link https://leetcode.cn/problems/remove-element/
 */
function removeElement(nums: number[], val: number): number {
  let fastIndex = 0;
  let slowIndex = 0;

  while (fastIndex < nums.length) {
    nums[slowIndex] = nums[fastIndex];
    if (nums[fastIndex] !== val) {
      slowIndex++;
    }
    fastIndex++;
  }
  console.log(nums, slowIndex);

  return slowIndex;
}

/**
 * @link https://leetcode.cn/problems/remove-duplicates-from-sorted-array/?envType=study-plan-v2&id=top-interview-150
 */
function removeDuplicates(nums: number[]): number {
  // 遍历数组
  let fastIndex = 0;
  // 指向有效数组下标
  let slowIndex = 0;
  let cmp = nums[0];

  while (cmp <= nums[nums.length - 1] && fastIndex < nums.length) {
    if (nums[fastIndex] === cmp) {
      nums[slowIndex] = nums[fastIndex];
      cmp++;
      slowIndex++;
    }
    if (nums[fastIndex] > cmp) {
      cmp = nums[fastIndex];
    } else {
      fastIndex++;
    }
  }
  console.log(nums, slowIndex);
  return slowIndex;
}

/**
 * @link https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii/?envType=study-plan-v2&id=top-interview-150
 */
function removeDuplicates2(nums: number[]): number {
  // 遍历数组
  let fastIndex = 0;
  // 指向有效数组下标
  let slowIndex = 0;
  let cmp = nums[0];
  let count = 0;

  while (cmp <= nums[nums.length - 1] && fastIndex < nums.length) {
    if (nums[fastIndex] === cmp) {
      nums[slowIndex] = nums[fastIndex];
      count++;
      if (count === 2) {
        cmp++;
        count = 0;
      }
      slowIndex++;
    }
    if (nums[fastIndex] > cmp) {
      cmp = nums[fastIndex];
      count = 0;
    } else {
      fastIndex++;
    }
  }
  console.log(nums, slowIndex);
  return slowIndex;
}

/**
 * @link https://leetcode.cn/problems/majority-element/?envType=study-plan-v2&id=top-interview-150
 */
function majorityElement(nums: number[]): number {
  let cmp = nums.length / 2;
  let dic: object = {};
  nums.map((n) => {
    dic.hasOwnProperty(n) ? (dic as any)[n]++ : ((dic as any)[n] = 1);
  });
  let res = 0;
  Object.keys(dic).map((k) => {
    if ((dic as any)[k] > cmp) {
      res = Number(k);
    }
  });
  console.log(res);

  return res;
}

/**
 * @link https://leetcode.cn/problems/rotate-array/?envType=study-plan-v2&id=top-interview-150
 */
function rotate(nums: number[], k: number): void {
  console.log(nums.slice(0, -k), nums.slice(-k));
  while (k > nums.length) {
    k -= nums.length;
  }

  [...nums.slice(-k), ...nums.slice(0, -k)].map((v, i) => {
    nums[i] = v;
  });
  console.log(nums);
}

/**
 * @link https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/?envType=study-plan-v2&id=top-interview-150
 */
function maxProfit(prices: number[]): number {
  let res: number = 0;
  let st: number[] = [prices[0]];

  for (let i = 1; i < prices.length; i++) {
    if (st.length && prices[i] >= st[st.length - 1]) {
      res = Math.max(res, prices[i] - st[st.length - 1]);
    } else {
      st.push(prices[i]);
    }
  }

  console.log(st, res);

  return res;
}

/**
 * @link https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/?envType=study-plan-v2&id=top-interview-150
 */
function maxProfit2(prices: number[]): number {
  // dynamic planning
  // let dp: number[][] = Array(prices.length)
  //   .fill(null)
  //   .map((v) => (v = Array(2).fill(null)));

  // // 初始状态
  // dp[0][0] = 0;
  // dp[0][1] = -prices[0];
  // for (let i = 1; i < prices.length; i++) {
  //   dp[i][0] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][0]);
  //   dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1]);
  // }
  // console.log(dp);
  // return dp[prices.length - 1][0];

  // greedy
  let ans = 0;
  for (let i = 1; i < prices.length; i++) {
    ans += Math.max(0, prices[i] - prices[i - 1]);
  }
  console.log(ans);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/jump-game/?envType=study-plan-v2&id=top-interview-150
 */
function canJump(nums: number[]): boolean {
  // greedy
  // let farest = 0;
  // for (let i = 0; i < nums.length; i++) {
  //   if (i > farest) return false;
  //   farest = Math.max(farest, i + nums[i]);

  //   if (farest >= nums.length - 1) {
  //     return true;
  //   }
  // }
  // return false;

  // dp
  let dp = Array(nums.length).fill(false);
  dp[0] = true;
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && j + nums[j] > i) {
        dp[i] = true;
      }
    }
  }
  return dp[nums.length];
}

/**
 * @link https://leetcode.cn/problems/jump-game-ii/?envType=study-plan-v2&id=top-interview-150
 */
function jump(nums: number[]): number {
  let maxPos = 0;
  let end = 0;
  let ans: number = 0;
  for (let i = 0; i < nums.length; i++) {
    maxPos = Math.max(maxPos, i + nums[i]);
    if (i === end) {
      end = maxPos;
      ans++;
    }
  }
  return ans;
}

/**
 * @link https://leetcode.cn/problems/h-index/?envType=study-plan-v2&id=top-interview-150
 */
function hIndex(citations: number[]): number {
  citations.sort((a, b) => b - a);
  console.log(citations);
  let ans = 0;
  for (let i = 0; i < citations.length; i++) {
    if (citations[i] > ans) {
      ans += 1;
    }
  }
  return ans;
}

/**
 * @link https://leetcode.cn/problems/product-of-array-except-self/solution/chu-zi-shen-yi-wai-shu-zu-de-cheng-ji-by-leetcode-/
 */
function productExceptSelf(nums: number[]): number[] {
  let L = [1];
  let R = [1];
  let ans = [];
  for (let i = 0; i < nums.length - 1; i++) {
    L.push(nums[i] * L[i]);
  }
  nums = nums.reverse();
  console.log(nums);

  for (let i = 0; i < nums.length - 1; i++) {
    R.push(nums[i] * R[i]);
  }
  R = R.reverse();
  for (let i = 0; i < nums.length; i++) {
    ans.push(L[i] * R[i]);
  }
  return ans;
}

function longestCommonPrefix(strs: string[]): string {
  let len = strs[0].length;
  let cmp = "";
  let ans = "";
  for (let i = 0; i < len; i++) {
    cmp += strs[0][i];
    let flag = false;
    for (let j = 0; j < strs.length; j++) {
      if (strs[j].indexOf(cmp) === 0) {
      } else {
        flag = true;
        break;
      }
    }
    if (flag) {
      break;
    }
    ans = cmp;
  }
  console.log(ans);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/gas-station/submissions/
 */
function canCompleteCircuit(gas: number[], cost: number[]): number {
  let totalGas = 0;
  let totalCost = 0;
  for (let i = 0; i < gas.length; i++) {
    totalCost += cost[i];
    totalGas += gas[i];
  }
  if (totalGas < totalCost) {
    return -1;
  }
  let remian = 0;
  let start = 0;
  for (let i = 0; i < gas.length; i++) {
    remian = remian - cost[i] + gas[i];
    if (remian < 0) {
      remian = 0;
      start = i + 1;
    }
  }
  return start;
}

/**
 * @link https://leetcode.cn/problems/candy/?envType=study-plan-v2&envId=top-interview-150
 */
function candy(ratings: number[]): number {
  let indexes = Array.from(new Set([...ratings].sort()));
  let ans = 0;
  let candies = Array(ratings.length).fill(1);

  while (indexes.length) {
    let cmp = indexes.shift();
    for (let i = 0; i < ratings.length; i++) {
      if (ratings[i] === cmp) {
        if (i - 1 >= 0 && ratings[i] < ratings[i - 1]) {
          candies[i - 1] =
            candies[i] + 1 >= candies[i - 1] ? candies[i] + 1 : candies[i - 1];
        }
        if (i + 1 <= ratings.length - 1 && ratings[i] < ratings[i + 1]) {
          candies[i + 1] =
            candies[i] + 1 >= candies[i + 1] ? candies[i] + 1 : candies[i + 1];
        }
      }
    }
  }
  candies.map((i) => (ans += i));

  return ans;
}

/**
 * @link https://leetcode.cn/problems/insert-delete-getrandom-o1/?envType=study-plan-v2&id=top-interview-150
 */
class RandomizedSet {
  list: Array<number>;
  map: Object;

  constructor() {
    this.list = [];
    this.map = {};
  }

  insert(val: number): boolean {
    if (this.list.includes(val)) {
      return false;
    }
    this.list.push(val);
    return true;
  }

  remove(val: number): boolean {
    if (this.list.includes(val)) {
      this.list.splice(this.list.indexOf(val), 1);
      return true;
    }
    return false;
  }

  getRandom(): number {
    return this.list[Math.floor(Math.random() * this.list.length)];
  }
}

/**
 * @link https://leetcode.cn/problems/roman-to-integer/?envType=study-plan-v2&envId=top-interview-150
 */
function romanToInt(s: string): number {
  let romanDict: any = {
    I: 1,
    V: 5,
    X: 10,
    L: 50,
    C: 100,
    D: 500,
    M: 1000,
  };
  let ans = 0;
  let index = s.length - 1;
  let st = [s[index]];
  index -= 1;
  while (index >= 0) {
    while (romanDict[st[st.length - 1]] < romanDict[s[index]]) {
      console.log(st[st.length - 1]);
      ans += romanDict[st[st.length - 1]];
      st.pop();
    }
    if (romanDict[st[st.length - 1]] > romanDict[s[index]]) {
      ans += romanDict[st[st.length - 1]] - romanDict[s[index]];
      st.pop();
      index -= 1;
    }
    index >= 0 && st.push(s[index]);
    index -= 1;
  }

  while (st.length) {
    ans += romanDict[st[st.length - 1]];
    st.pop();
  }
  console.log(ans, st);
  return ans;
}

/**
 * @link https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-interview-150
 */
function trap(height: number[]): number {
  // dp
  // let leftMax: number[] = Array(height.length).fill(undefined);
  // let rightMax: number[] = Array(height.length).fill(undefined);
  // leftMax[0] = height[0];
  // rightMax[height.length - 1] = height[height.length - 1];
  // for (let i = 1; i < height.length; i++) {
  //   leftMax[i] = Math.max(leftMax[i - 1], height[i]);
  // }
  // for (let i = height.length - 2; i >= 0; i--) {
  //   rightMax[i] = Math.max(rightMax[i + 1], height[i]);
  // }
  // let dp: number[] = Array(height.length).fill(0);
  // for (let i = 0; i < height.length; i++) {
  //   dp[i] = Math.min(leftMax[i], rightMax[i]) - height[i];
  // }
  // console.log(leftMax, rightMax, dp);
  // let ans = 0;
  // dp.map((i) => (ans += i));
  // return ans;

  // monotone stack
  let ans = 0;
  let stack: number[] = [];
  for (let i = 0; i < height.length; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      let top = stack.pop() as number;
      if (!stack.length) {
        break;
      }
      let left = stack[stack.length - 1];
      ans += (i - left - 1) * (Math.min(height[i], height[left]) - height[top]);
    }
    stack.push(i);
  }

  console.log(ans);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/length-of-last-word/?envType=study-plan-v2&envId=top-interview-150
 */
function lengthOfLastWord(s: string): number {
  return s.trim().split(" ").pop()?.length ?? 0;
}

/**
 * @link https://leetcode.cn/problems/reverse-words-in-a-string/?envType=study-plan-v2&envId=top-interview-150
 */
function reverseWords(s: string): string {
  return s.trim().split(" ").reverse().join(" ").replace(/\s+/g, " ");
}

/**
 * @link https://leetcode.cn/problems/integer-to-roman/?envType=study-plan-v2&envId=top-interview-150
 */
function intToRoman(num: number): string {
  let romanDict: [number, string][] = [
    [1000, "M"],
    [900, "CM"],
    [500, "D"],
    [400, "CD"],
    [100, "C"],
    [90, "XC"],
    [50, "L"],
    [40, "XL"],
    [10, "X"],
    [9, "IX"],
    [5, "V"],
    [4, "IV"],
    [1, "I"],
  ];

  let ans = "";
  for (let [value, text] of romanDict) {
    while (num >= value) {
      num -= value;
      ans += text;
    }
  }
  console.log(ans);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/zigzag-conversion/?envType=study-plan-v2&envId=top-interview-150
 */
function convert(s: string, numRows: number): string {
  let ans = "";

  let zList: string[][] = Array(numRows).fill(0);
  for (let i = 0; i < zList.length; i++) {
    zList[i] = [];
  }

  let x = 0;
  let flag = false;
  let cmp = numRows - 2;
  for (let i = 0; i < s.length; i++) {
    zList[x].push(s[i]);
    if (flag) {
      x -= 1;
    } else {
      x += 1;
    }
    if (x > numRows - 1) {
      x -= 2;
      flag = true;
    }
    if (x < 0) {
      x += 2;
      flag = false;
    }
  }
  console.log(zList);

  for (let i = 0; i < zList.length; i++) {
    for (let j = 0; j < zList[i].length; j++) {
      ans += zList[i][j];
    }
  }
  console.log(ans);

  return ans;
}

/**
 * @link https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/?envType=study-plan-v2&envId=top-interview-150
 */
function strStr(haystack: string, needle: string): number {
  // indexOf
  // return haystack.indexOf(needle);
  // KMP algorithm
  return 0;
}

/**
 * @link https://leetcode.cn/problems/text-justification/description/?envType=study-plan-v2&envId=top-interview-150
 */
function fullJustify(words: string[], maxWidth: number): string[] {
  let ans: string[] = [];

  if (words.length === 1) {
    let tmp = words[0];
    for (let i = 0; i < maxWidth - words[0].length; i++) {
      tmp += " ";
    }
    return [tmp];
  }

  let left = 0;

  let right = 1;

  while (left < words.length) {
    let characterNum = words[left].length;
    while (
      right < words.length &&
      words[right].length + characterNum + 1 <= maxWidth
    ) {
      characterNum += words[right].length + 1;
      right++;
    }

    // 到结尾未超过作为最后一行
    if (right >= words.length) {
      let tmp = words[left];
      for (let i = left + 1; i < right; i++) {
        tmp += " " + words[i];
      }
      for (let i = 0; i < maxWidth - characterNum; i++) {
        tmp += " ";
      }
      ans.push(tmp);
    } else {
      if (right - left === 1) {
        let tmp = words[left];
        for (let i = 0; i < maxWidth - characterNum; i++) {
          tmp += " ";
        }
        ans.push(tmp);
      } else {
        // 计算平均空格
        let avgSpace =
          (maxWidth - characterNum + (right - left - 1)) / (right - left - 1);
        console.log("avgSpace:", avgSpace, avgSpace % 1);
        if (avgSpace % 1 !== 0) {
          let offset =
            (maxWidth - characterNum + (right - left - 1)) % (right - left - 1);
          avgSpace =
            (maxWidth - characterNum + (right - left - 1) - offset) /
            (right - left - 1);
          console.log("avgSpace: ", avgSpace, "offset: ", offset);
          let tmp = words[left];
          for (let i = left + 1; i < right; i++) {
            if (offset) {
              tmp += " ";
              offset--;
            }

            for (let j = 0; j < avgSpace; j++) {
              tmp += " ";
            }
            tmp += words[i];
          }
          ans.push(tmp);
        } else {
          let tmp = words[left];
          for (let i = left + 1; i < right; i++) {
            for (let j = 0; j < avgSpace; j++) {
              tmp += " ";
            }
            tmp += words[i];
          }
          ans.push(tmp);
        }
      }
    }
    console.log(left, right, ans);
    left = right;
    right = left + 1;
  }

  return ans;
}

export default {
  merge,
  removeElement,
  removeDuplicates,
  removeDuplicates2,
  majorityElement,
  rotate,
  maxProfit,
  maxProfit2,
  canJump,
  jump,
  hIndex,
  productExceptSelf,
  longestCommonPrefix,
  canCompleteCircuit,
  candy,
  trap,
  lengthOfLastWord,
  reverseWords,
  RandomizedSet,
  romanToInt,
  intToRoman,
  convert,
  strStr,
  fullJustify,
};
